import jdk.nashorn.internal.ir.CallNode;

public class sparseArr {
    public static void main(String[] args) {
        MakeNode makeNode = new MakeNode();
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        makeNode.addElement(node2);
        makeNode.addElement(node3);
        makeNode.addElement(node4);
        makeNode.addElement(node5);
        makeNode.showElement();
    }
}
class DoubleLinkedList{
    Element head = new Element(0);
    //删除双向链表元素
    public void delElement(int num){
        Element point = head.next;
        while(true){
            if(num == point.num){
                break;
            }
            if(point == null){
                System.out.println("未找到...");
                return;
            }
            point = point.next;
        }
        //双向链表会存在point.next为空的现象，故当使用pre的时候需要判断
        if(point.next == null){
            point.pre.next = null;
        }else {
            point.pre.next = point.next;
            point.next.pre = point.pre;
        }
    }
    //添加双向链表元素
    public void addElement(Element element){
        Element point = head;
        while (true){
            if(point.next == null){
                break;
            }
            if(point.next.num >= element.num){
                break;
            }
            point = point.next;
        }
        element.next = point.next;
        if(point.next != null) {
            point.next.pre = element;
        }
        point.next = element;
        element.pre = point;
    }
    //显示双向链表元素
    public void showElement(){
        Element point = head.next;
        while(true){
            if(point == null){
                break;
            }
            System.out.println(point);
            point = point.next;
        }
    }
}
class Element{
    int num;
    Element next;
    Element pre;
    public Element(int num){
        this.num = num;
    }
    public String toString(){
        return num + "";
    }
}
class LinkedList{
    Hero head = new Hero(0," ");
    //新浪面试题：寻找倒数第k个链表元素
    public void findElement(int k){
        //常规方法
        Hero point = head.next;
        int num = 1;
        //遍历链表，得出链表元素个数
        while(point.next != null) {
            num++;
            point = point.next;
        }
        point = head.next;
        for(int i = 1;i<=num-k;i++){
            point = point.next;
        }
        System.out.println(point);
        //双指针法
        Hero point1 = head;
        Hero point2 = head;
        for(int i = 0;i<k;i++){
            point1 = point1.next;
        }
        for(int i = 0;point1.next!=null;i++){
            point1 = point1.next;
            point2 = point2.next;
        }
        System.out.println(point2.next);
    }
    //腾讯面试题：反转链表
    public void revereList(){
        Hero point1 = head.next;
        Hero head1 = new Hero(0," ");
        Hero emo = null;
        while(true){
            Hero tamp = point1;
            point1 = point1.next;
            head1.next = tamp;
            tamp.next = emo;
            emo = tamp;
            if(point1==null){
                break;
            }
        }
        head.next = head1.next;
    }
    //百度面试题：反转打印
    public void afterPaint(){
        boolean loop = true;
        Hero pointer = head;
        int num=0;
        while(true){
            num++;
            pointer = pointer.next;
            if(pointer.next == null){
                break;
            }
        }
        //System.out.println(num);
        while(loop) {
            pointer = head;
            for (int i = 0; i < num; i++) {
                pointer = pointer.next;
            }
            num--;
            System.out.print(pointer);
            if(num==0){
                loop = false;
            }
        }
    }
    //删除链表元素
    public void cutLinkedList(int num){
        //设置boolean变量，若找到了，则true，不然不变
        boolean findNull = false;
        Hero point = head;
        while(true){
            if(num == point.next.num){
                findNull = true;
                break;
            }
            point = point.next;
        }
        if(findNull){
            point.next = point.next.next;
            showLinkedList();
        }else{
            System.out.println("无");
        }
    }
    //增加链表元素
    public void addLinkedList(Hero hero){
        Hero point = head;
        while(true) {
            if (point.next == null) {
                break;
            }
            if (point.next.num > hero.num) {
                break;
            }
            point = point.next;
        }
        hero.next = point.next;
        point.next = hero;
    }
    //显示链表
    public void showLinkedList(){
        Hero point = head;
        while(true) {
            if(point.next == null){
                break;
            }
            System.out.print(point.next);
            point = point.next;
        }
    }
}
class Hero{
    public int num;
    public String name;
    public Hero next;
    public Hero(int num,String name){
        this.name=name;
        this.num = num;
    }
    public String toString(){
        return "["+num + name +"]";
    }
}
class Node{
    int num;
    Node next;
    public Node(int num){
        this.num = num;
    }
    public String toString(){
        return num + " ";
    }
}
class MakeNode{
    Node head = new Node(1);
    Node first = null;
    Node second=null;
    public MakeNode(){
        this.first = head;
        this.second = head;
        second.next = first;
    }
    public void addElement(Node element){
        while(true){
            //second.next = element;
            if(second.next == first){
                second.next = element;
                second = second.next;
                second.next = first;
                break;
            }
            second = second.next;
        }
    }
    public void showElement(){
        first = head;
        second = head;
        System.out.print(first);
        System.out.print(" ");
        while(true){
            second = second.next;
            if(second == first){
                break;
            }else{
                System.out.print(second);
                System.out.print(" ");
            }
        }
    }
}